CODE 135. Copy List with Random Pointer

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/23/2013-11-23-CODE 135 Copy List with Random Pointer/

访问原文「CODE 135. Copy List with Random Pointer」

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.

public RandomListNode copyRandomList(RandomListNode head) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	Map<Integer, RandomListNode> map = new HashMap<Integer, RandomListNode>();

	RandomListNode cpyList = new RandomListNode(0);
	RandomListNode cpyListTmp = cpyList;
	RandomListNode headTmp = head;
	while (null != headTmp) {
		int val = headTmp.label;
		if (map.containsKey(val)) {
			RandomListNode newnode = map.get(val);
			cpyListTmp.next = newnode;
			cpyListTmp = cpyListTmp.next;
			headTmp = headTmp.next;
		} else {
			RandomListNode newnode = new RandomListNode(val);
			cpyListTmp.next = newnode;
			cpyListTmp = cpyListTmp.next;
			headTmp = headTmp.next;
			map.put(val, newnode);
		}
	}
	cpyListTmp = cpyList;
	headTmp = head;
	while (null != headTmp) {
		if (null == headTmp.random) {
			cpyListTmp.next.random = null;
		} else {
			cpyListTmp.next.random = map.get(headTmp.random.label);
		}
		cpyListTmp = cpyListTmp.next;
		headTmp = headTmp.next;
	}
	return cpyList.next;
}